import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:找到字符串中所有字母异位词
 * User: bjc
 * Date: 2025-11-12
 * Time: 17:55
 */
public class Test06_findAnagrams {
    //暴力解
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) return list;
        //因为字符串中字母都是小写的，对应ascii值是97-122，长度最大是26，所以创建一个长度为26的数组表示哈希表
        int[] hash = new int[26];
        int len = p.length();

        // 统计字符串p中各字符出现次数
        for (int i = 0; i < len; i++) {
            hash[p.charAt(i) - 'a']++;
        }

        // 遍历字符串s的所有子串
        for (int i = 0; i <= s.length() - len; i++) {
            int[] tmp = new int[26];
            // 统计当前子串中各字符出现次数
            for (int j = 0; j < len; j++) {
                tmp[s.charAt(i + j) - 'a']++;
            }

            // 比较两个数组是否相等
            boolean isAnagram = true;
            for (int k = 0; k < 26; k++) {
                if (hash[k] != tmp[k]) {
                    isAnagram = false;
                    break;
                }
            }

            if (isAnagram) {
                list.add(i);
            }
        }
        return list;
    }

    //滑动窗口+哈希表
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) return list;
        //将字符串转为字符数组
        char[] chars = s.toCharArray();
        char[] charp = p.toCharArray();
        int len = charp.length;
        int[] hash_p = new int[26]; // 统计字符串p中各字符出现次数
        int[] hash_s = new int[26]; // 统计字符串s中各字符出现次数
        for (int i = 0; i < len; i++) {
            hash_p[charp[i] - 'a']++;
        }
        int left = 0, right = 0;
        while (right < chars.length){
            //进窗口
            char in = chars[right];
            hash_s[in - 'a']++;
            //判断是否出窗口
            if (right - left + 1 > len) {
                //出窗口
                char out = chars[left];
                hash_s[out - 'a']--;
                left++;
            }
            //更新结果
            if (right - left + 1 == len) {
                //检查此时的hash_p和hash_s元素是否相等
                boolean ret = check(hash_p, hash_s);
                if (ret){
                    list.add(left);
                }
            }
            right++;
        }
        return list;
    }


    private boolean check(int[] hashP, int[] hashS) {
        boolean isAnagram = true;
        for (int i = 0; i < 26; i++) {
            if (hashP[i] != hashS[i]) {
                isAnagram = false;
                break;
            }
        }
        return isAnagram;
    }
    //滑动窗口+哈希表:优化更新结果
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) return list;
        //将字符串转为字符数组
        char[] chars = s.toCharArray();
        char[] charp = p.toCharArray();
        int len = charp.length;
        int[] hash_p = new int[26]; // 统计字符串p中各字符出现次数
        int[] hash_s = new int[26]; // 统计字符串s中各字符出现次数
        for (int i = 0; i < len; i++) {
            hash_p[charp[i] - 'a']++;
        }
        int left = 0, right = 0;
        int count = 0; //记录窗口中有效字符个数
        while (right < chars.length){
            //进窗口
            char in = chars[right];
            //hash_s[in - 'a']++;
            //更新count
            if(hash_p[in - 'a'] > hash_s[in - 'a']++){
                count++;
            }

            //判断是否出窗口
            if (right - left + 1 > len) {
                //出窗口
                char out = chars[left];
                //更新count
                if(hash_p[out - 'a'] >= hash_s[out - 'a']--){
                    //说明移除窗口元素是有效字符，所以需要更新count
                    count--;
                }
                //hash_s[out - 'a']--;
                left++;
            }
            //更新结果
            if(count == len) list.add(left);
            right++;
        }
        return list;
    }
}
